package sword.offer.breakthrough;

/**
 * 给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。
 * 输入: n = 5
 * 输出: [0,1,1,2,1,2]
 * 解释:
 * 0 --> 0
 * 1 --> 1
 * 2 --> 10
 * 3 --> 11
 * 4 --> 100
 * 5 --> 101
 *
 * 链接：https://leetcode-cn.com/problems/w3tCBm
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class Third {

    /**
     * 通过观察，我们发现任意一个数的2的n次幂数 二进制表示的1是一样多的。
     * 比如 2 和 4  和 8 都是一个1  3 和 6  和 12 都是 两个1
     * 而对于奇数来说，它二进制为1的位数是上一位偶数的 + 1。 比如 9有2位1 , 其由来为8 + 1
     * */
    class Solution {
        public int[] countBits(int n) {
            if(n == 0){
                return new int[]{0};
            }
            int[] dp = new int[n+1];
            dp[0] = 0;
            dp[1] = 1;
            for (int i = 2; i <= n; i++) {
                if(i % 2 == 0){
                    dp[i] = dp[i >> 1];
                }else{
                    dp[i] = dp[i] + 1;
                }
            }
            return dp;
        }
    }
}
